/** 递增排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 */

function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    
    /** 将数组拆成两组 */
    const mid = Math.floor(arr.length / 2);
    // 左半部分（不包含mid下标）
    const left = arr.slice(0, mid);
    // 右半部分
    const right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

/** 合并两个有序数组为一个有序数组 */
function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    // 比较左右数组的元素，谁小就push到result数组
    while(i < left.length && j < right.length) {
        if(left[i] <= right[j]) {
            result.push(left[i++]);
        }else {
            result.push(right[j++]);
        }
    }
    
    // 把剩下部分加起来
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// 测试
const arr = [5, 2, 4, 1, 3];
const sorted = mergeSort(arr);
console.log(sorted);
